package com.company.笔试.常用排序算法.归并;

import com.company.笔试.常用排序算法.array.ArrayData;

import java.util.Arrays;

/**
 * @author ylr
 * @version 1.0.0
 * @ClassName MargeSortTest1.java  随心默写1次
 * @Description TODO
 * @createTime 2022年02月25日 09:36:00
 */
public class MargeSortTest1 {
    public static void main(String[] args) {
        int[] a = new ArrayData().getA();
        //22,41,7,33,12,60,57,43,17
        MargeSortTest1 margeSortTest1 = new MargeSortTest1();
        margeSortTest1.sort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    public int[] sort(int[] arr, int left, int right) {
        if (left>=right||arr==null) return arr; //第一步判断递归跳出的条件是左下标大于等于右下标,或者arr为空
        int mid = (left + right) / 2;   //第二部取中点
        sort(arr, left, mid);    //递归二分左
        sort(arr, mid + 1, right);  //递归二分右
        marge(arr, left,right);//合并左右
        return arr;
    }
    public void marge(int[] arr, int left, int right) {// 01, 41
        int[] tmp = new int[right-left+1];//保存左右两边的有序数组
        int mid = (left + right) / 2;   //取中点
        int l = left; //左遍历起点
        int r = mid+1;//右遍历起点
        int t = 0;//有序数组起点
        //遍历比较
        while (l<=mid&&r<=right) {
            tmp[t++]=arr[l]<=arr[r]?arr[l++]:arr[r++];
        }
        //剩余
        while (l<=mid) {
            tmp[t++]=arr[l++];
        }
        while (r<=right) {
            tmp[t++]=arr[r++];
        }

        //有序数组合并进arr中
        for (int i = 0; i < tmp.length; i++) {
            arr[left++]=tmp[i];
        }
    }
}
